// 教科书中的朴素哈希表实现
// 相比于hashSet，它可以允许用户自定义key值存储
// 这里同样采取了底层数组搭配链表的实现
// 不同之处在于在数组中初始化了所有的哨兵节点

import { HashTableContent, KeyValuePair } from './type';

// 链表节点类定义
class Node<T, U> implements HashTableContent<T, U>{
    key: T;
    value: U;
    next: null | Node<T, U>;
    constructor(key: T, value: U) {
        this.key = key;
        this.value = value;
        this.next = null;
    }
}

// 哈希表类定义
export class HashTable<T = unknown, U = unknown>{
    protected size: number;
    protected table: Node<T, U>[];
    private initialSize: number;
    // 构造函数
    constructor(size: number) {
        this.table = this.initTable(size);// 在各个位置初始化哨兵节点
        this.size = 0;
        this.initialSize = size;
    }
    // 初始化哨兵节点
    private initTable(size: number) {
        const table: Node<T, U>[] = [];
        for (let i = 0; i < size; i++) {
            table.push(new Node<unknown, unknown>(0, null) as Node<T, U>);
        }
        return table;
    }
    // 计算哈希值
    protected getHashCode(value: T): number {
        let hashStr = '';// 哈希字符
        // 判断是不是复杂数据类型
        if (value instanceof Object) {
            hashStr = Object.prototype.toString.call(value);
        } else {
            hashStr = String(value);
        }
        return hashStr.charCodeAt(0) % this.table.length;
    }
    // 存储方法
    set(key: T, value: U): void {
        const storeIndex = this.getHashCode(key);
        let matchPair = this.table[storeIndex];
        // 检查是否出现了重复的key值
        while (matchPair.next) {
            const nextPair = matchPair.next;
            if (nextPair.key === key) {
                nextPair.value = value;
                return;
            }
            matchPair = nextPair;
        }
        matchPair.next = new Node(key, value);
        this.size++;
    }
    // 根据key值拿value值
    get(key: T): U | null {
        const storeIndex = this.getHashCode(key);
        let matchPair = this.table[storeIndex];// 哨兵节点
        while (matchPair.next) {
            const nextPair = matchPair.next;
            if (nextPair.key === key) {
                return nextPair.value;
            }
            matchPair = nextPair;
        }
        return matchPair.value;
    }
    // 根据key值删除方法
    remove(key: T): boolean {
        const storeIndex = this.getHashCode(key);
        let matchPair = this.table[storeIndex];// 哨兵节点
        while (matchPair.next) {
            const nextPair = matchPair.next;
            if (nextPair.key === key) {
                matchPair.next = nextPair.next;
                this.size--;
                return true;
            }
            matchPair = nextPair;
        }
        return false;
    }

    // 返回哈希表长度方法
    length(): number {
        return this.size;
    }

    // 重置方法
    reset(size: number = this.initialSize): void {
        this.table = this.initTable(size);// 重新初始化哨兵节点
        this.size = 0;
        this.initialSize = size;
    }

    // 展示方法
    show(): void {
        const exists: KeyValuePair<T, U>[] = [];
        for (let i = 0; i < this.table.length; i++) {
            let currPair = this.table[i];
            while (currPair.next) {
                const { key, value } = currPair.next;
                exists.push({ key, value });
                currPair = currPair.next;
            }
        }
        console.log(...exists);
    }

}



// 测试用例
const ht = new HashTable(10);
console.log(ht.set('1', 1))
console.log(ht.set('aa', 2))
console.log(ht.set('6a', 3))
console.log(ht.set('75', 4))
console.log(ht.set('aa', 5));
console.log(ht.set(1, 6));
console.log(ht.get('1'));// 1
console.log(ht.get('2'));// null
console.log(ht.set(false, 7));
console.log(ht.set(true, 8));
console.log(ht.remove(true));// true
console.log(ht.remove(12));// false
console.log(ht.set({ a: 1, b: 2 }, 9));
console.log('size:' + ht.length());// 7
ht.show();
ht.reset(4);
ht.show();